{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Shortest Distance from All Buildings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #breadth-first-search #array #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #广度优先搜索 #数组 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: shortestDistance"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #离建筑物最近的距离"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个 <code>m × n</code> 的网格，值为 <code>0</code> 、 <code>1</code> 或 <code>2</code> ，其中:</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>每一个 <code>0</code> 代表一块你可以自由通过的 <strong>空地</strong>&nbsp;</li>\n",
    "\t<li>每一个 <code>1</code> 代表一个你不能通过的 <strong>建筑</strong></li>\n",
    "\t<li>每个 <code>2</code> 标记一个你不能通过的 <strong>障碍</strong>&nbsp;</li>\n",
    "</ul>\n",
    "\n",
    "<p>你想要在一块空地上建造一所房子，在 <strong>最短的总旅行距离</strong> 内到达所有的建筑。你只能上下左右移动。</p>\n",
    "\n",
    "<p>返回到该房子的 <strong>最短旅行距离</strong> 。如果根据上述规则无法建造这样的房子，则返回 <code>-1</code> 。</p>\n",
    "\n",
    "<p><strong>总旅行距离&nbsp;</strong>是朋友们家到聚会地点的距离之和。</p>\n",
    "\n",
    "<p>使用 <strong>曼哈顿距离</strong>&nbsp;计算距离，其中距离 <code>(p1, p2) = |p2.x - p1.x | + | p2.y - p1.y |</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例&nbsp; 1：</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/03/14/buildings-grid.jpg\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]]\n",
    "<strong>输出：</strong>7 \n",
    "<strong>解析：</strong>给定<code>三个建筑物 (0,0)、</code><code>(0,4) 和</code> <code>(2,2) 以及一个</code>位于 <code>(0,2) 的障碍物。\n",
    "由于总距离之和 3+3+1=7 最优，所以位置</code> <code>(1,2)</code> 是符合要求的最优地点。\n",
    "故返回7。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> grid = [[1,0]]\n",
    "<strong>输出:</strong> 1\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> grid = [[1]]\n",
    "<strong>输出:</strong> -1\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == grid.length</code></li>\n",
    "\t<li><code>n == grid[i].length</code></li>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 50</code></li>\n",
    "\t<li><code>grid[i][j]</code>&nbsp;是&nbsp;<code>0</code>,&nbsp;<code>1</code>&nbsp;或&nbsp;<code>2</code></li>\n",
    "\t<li><code>grid</code>&nbsp;中 <strong>至少</strong>&nbsp;有 <strong>一幢</strong> 建筑</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [shortest-distance-from-all-buildings](https://leetcode.cn/problems/shortest-distance-from-all-buildings/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [shortest-distance-from-all-buildings](https://leetcode.cn/problems/shortest-distance-from-all-buildings/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]]', '[[1,0]]', '[[1]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestDistance(self, grid: List[List[int]]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        dis=[[0 for _ in range(n)] for _ in range(m)]\n",
    "        ls=[]\n",
    "        d=[(1,0),(0,1),(-1,0),(0,-1)]\n",
    "        find=False\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==1:\n",
    "                    ls.append((i,j))\n",
    "                    grid[i][j]=-1\n",
    "                elif grid[i][j]==2:\n",
    "                    grid[i][j]=-2\n",
    "                else:\n",
    "                    find=True \n",
    "        if not find:\n",
    "            return -1\n",
    "        def bfs(x,y):\n",
    "            q=collections.deque()\n",
    "            q.append((x,y,0))\n",
    "            g=copy.deepcopy(grid)\n",
    "            #print(g)\n",
    "            while q:\n",
    "                a,b,dist=q.popleft()\n",
    "                if (a,b)!=(x,y) and g[a][b]!=0:\n",
    "                    continue\n",
    "                if (a,b)!=(x,y):\n",
    "                    g[a][b]=dist\n",
    "                for da,db in d:\n",
    "                    aa=a+da\n",
    "                    bb=b+db\n",
    "                    if 0<=aa<m and 0<=bb<n:\n",
    "                        q.append((aa,bb,dist+1))\n",
    "            #print(g)\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if g[i][j]==0:\n",
    "                        dis[i][j]=-float(\"inf\")\n",
    "                    if g[i][j]<0:\n",
    "                        continue\n",
    "                    dis[i][j]+=g[i][j]\n",
    "        for a,b in ls:\n",
    "            bfs(a,b)\n",
    "        ans=float(\"inf\")\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if dis[i][j]<=0:\n",
    "                    continue\n",
    "                if dis[i][j]<ans:\n",
    "                    #print(i,j)\n",
    "                    ans=dis[i][j]\n",
    "        if ans!=float(\"inf\"):\n",
    "            return ans\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestDistance(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        friends = []\n",
    "\n",
    "        def valid(i, j):\n",
    "            return 0 <= i < m and 0 <= j < n \n",
    "\n",
    "        dir = [[0, 1], [1, 0], [0, -1], [-1, 0]]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    friends.append([i, j])\n",
    "                    grid[i][j] = inf \n",
    "                elif grid[i][j] == 2:\n",
    "                    grid[i][j] = inf \n",
    "        \n",
    "        def bfs(i, j):\n",
    "            dq = deque([[i, j, 0]])\n",
    "            mat = [[0] * n for _ in range(m)]\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if grid[i][j] == inf:\n",
    "                        mat[i][j] = inf \n",
    "            while dq:\n",
    "                for _ in range(len(dq)):\n",
    "                    x, y, d = dq.popleft()\n",
    "                    for dx, dy in dir:\n",
    "                        nx, ny = x + dx, y + dy \n",
    "                        if valid(nx, ny) and mat[nx][ny] == 0:\n",
    "                            mat[nx][ny] = d + 1\n",
    "                            dq.append([nx, ny, d + 1])\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if mat[i][j] == 0: \n",
    "                        grid[i][j] = inf \n",
    "                    elif mat[i][j] != inf:\n",
    "                        grid[i][j] += mat[i][j]\n",
    "        \n",
    "        for i, j in friends:\n",
    "            bfs(i, j)\n",
    "        ans = inf \n",
    "        for i in range(m):\n",
    "            for j in range(n): \n",
    "                ans = min(ans, grid[i][j])\n",
    "        return ans if ans != inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestDistance(self, grid: List[List[int]]) -> int:\n",
    "        \"\"\"\n",
    "        思路：用一个matrix作为记录记录，记录0节点：能够到达该0节点的1的个数；达到该0节点的1的距离和。\n",
    "        然后遍历matrix矩阵，当几点0的到达该节点1的个数和总的1的个数相同时，就求最小和\n",
    "        \"\"\"\n",
    "        def dfs(i, j):\n",
    "            dq = []\n",
    "            dq.append((i, j, 0))\n",
    "            tmp = copy.deepcopy(grid)\n",
    "            while dq:\n",
    "                i, j, level = dq.pop(0)\n",
    "                for i, j in [[i, j + 1], [i, j - 1], [i + 1, j], [i - 1, j]]:\n",
    "                    if 0 <= i < m and 0 <= j < n and tmp[i][j] == 0:\n",
    "                        tmp[i][j] = level + 1\n",
    "                        cunt_from_1[i][j] += 1\n",
    "                        sum_from_1[i][j] += (level + 1)\n",
    "                        dq.append((i, j, level + 1))\n",
    "\n",
    "        # 剪枝\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        if m == 1 and n == 1:\n",
    "            return -1\n",
    "\n",
    "        cunt_from_1 = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        sum_from_1 = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        cunt_1 = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    cunt_1 += 1\n",
    "                    dfs(i, j)\n",
    "\n",
    "        res = float('inf')\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0 and cunt_from_1[i][j] == cunt_1:\n",
    "                    res = min(res, sum_from_1[i][j])\n",
    "        return res if res != float('inf') else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestDistance(self, grid: List[List[int]]) -> int:\n",
    "        \"\"\"\n",
    "        思路：用一个matrix作为记录记录，记录0节点：能够到达该0节点的1的个数；达到该0节点的1的距离和。\n",
    "        然后遍历matrix矩阵，当几点0的到达该节点1的个数和总的1的个数相同时，就求最小和\n",
    "        \"\"\"\n",
    "        def dfs(i, j):\n",
    "            dq = []\n",
    "            dq.append((i, j, 0))\n",
    "            tmp = copy.deepcopy(grid)\n",
    "            while dq:\n",
    "                i, j, level = dq.pop(0)\n",
    "                for i, j in [[i, j + 1], [i, j - 1], [i + 1, j], [i - 1, j]]:\n",
    "                    if 0 <= i < m and 0 <= j < n and tmp[i][j] == 0:\n",
    "                        tmp[i][j] = level + 1\n",
    "                        cunt_from_1[i][j] += 1\n",
    "                        sum_from_1[i][j] += (level + 1)\n",
    "                        dq.append((i, j, level + 1))\n",
    "\n",
    "        # 剪枝\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        if m == 1 and n == 1:\n",
    "            return -1\n",
    "\n",
    "        cunt_from_1 = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        sum_from_1 = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        cunt_1 = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    cunt_1 += 1\n",
    "                    dfs(i, j)\n",
    "\n",
    "        res = float('inf')\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0 and cunt_from_1[i][j] == cunt_1:\n",
    "                    res = min(res, sum_from_1[i][j])\n",
    "        return res if res != float('inf') else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def shortestDistance(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        # 统计建筑集合\n",
    "        houseSet = set()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    houseSet.add((i, j))\n",
    "        # 计算各空地的最小距离和（某建筑无法到达的空地的相邻空地必然也无法达到，直接不再遍历）\n",
    "        disMatrix = [[0] * n for _ in range(m)]\n",
    "        currValue = 0\n",
    "        for h in houseSet:\n",
    "            dq = deque()\n",
    "            dq.appendleft(h)\n",
    "            dis = 0\n",
    "            while dq:\n",
    "                dis += 1\n",
    "                size = len(dq)\n",
    "                for _ in range(size):\n",
    "                    cur = dq.pop()\n",
    "                    for dir in [(-1, 0), (1, 0), (0, -1), (0, 1)]:\n",
    "                        i = cur[0] + dir[0]\n",
    "                        j = cur[1] + dir[1]\n",
    "                        if 0 <= i < m and 0 <= j < n and grid[i][j] == currValue:\n",
    "                            disMatrix[i][j] += dis\n",
    "                            grid[i][j] -= 1\n",
    "                            dq.appendleft((i, j))\n",
    "            currValue -= 1\n",
    "        # 在可达所有建筑的空地中，找到最小距离和\n",
    "        ans = float('inf')\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == currValue:\n",
    "                    ans = min(ans, disMatrix[i][j])\n",
    "        if ans == float('inf'):\n",
    "            return -1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestDistance(self, grid: List[List[int]]) -> int:\n",
    "        \"\"\"\n",
    "        思路：用一个matrix作为记录记录，记录0节点：能够到达该0节点的1的个数；达到该0节点的1的距离和。\n",
    "        然后遍历matrix矩阵，当几点0的到达该节点1的个数和总的1的个数相同时，就求最小和\n",
    "        \"\"\"\n",
    "        def dfs(i, j):\n",
    "            dq = []\n",
    "            dq.append((i, j, 0))\n",
    "            tmp = copy.deepcopy(grid)\n",
    "            while dq:\n",
    "                i, j, level = dq.pop(0)\n",
    "                for i, j in [[i, j + 1], [i, j - 1], [i + 1, j], [i - 1, j]]:\n",
    "                    if 0 <= i < m and 0 <= j < n and tmp[i][j] == 0:\n",
    "                        tmp[i][j] = level + 1\n",
    "                        cunt_from_1[i][j] += 1\n",
    "                        sum_from_1[i][j] += (level + 1)\n",
    "                        dq.append((i, j, level + 1))\n",
    "\n",
    "        # 剪枝\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        if m == 1 and n == 1:\n",
    "            return -1\n",
    "\n",
    "        cunt_from_1 = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        sum_from_1 = copy.deepcopy(cunt_from_1)\n",
    "        cunt_1 = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    cunt_1 += 1\n",
    "                    dfs(i, j)\n",
    "\n",
    "        res = float('inf')\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0 and cunt_from_1[i][j] == cunt_1:\n",
    "                    res = min(res, sum_from_1[i][j])\n",
    "        return res if res != float('inf') else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def shortestDistance(self, grid):\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        buildings = sum(row.count(1) for row in grid)\n",
    "        distances = [[0] * n for _ in range(m)]\n",
    "        reach_count = [[0] * n for _ in range(m)]\n",
    "\n",
    "        def bfs(x, y):\n",
    "            visited = [[False] * n for _ in range(m)]\n",
    "            visited[x][y] = True\n",
    "            queue = deque([(x, y, 0)])\n",
    "            while queue:\n",
    "                i, j, dist = queue.popleft()\n",
    "                for ni, nj in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:\n",
    "                    if 0 <= ni < m and 0 <= nj < n and not visited[ni][nj]:\n",
    "                        visited[ni][nj] = True\n",
    "                        if grid[ni][nj] == 0:\n",
    "                            distances[ni][nj] += dist + 1\n",
    "                            reach_count[ni][nj] += 1\n",
    "                            queue.append((ni, nj, dist + 1))\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    bfs(i, j)\n",
    "        \n",
    "        min_distance = float('inf')\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0 and reach_count[i][j] == buildings:\n",
    "                    min_distance = min(min_distance, distances[i][j])\n",
    "        \n",
    "        return min_distance if min_distance != float('inf') else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestDistance(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0]) \n",
    "        D = [[0] * n for _ in range(m)]\n",
    "        cnt_from = [[0] * n for _ in range(m)]\n",
    "        cnt = 0 \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    Q = deque()\n",
    "                    Q.append((0, i, j))\n",
    "                    vis =  [[0] * n for _ in range(m)]\n",
    "                    vis[i][j] = 1\n",
    "                    cnt += 1 \n",
    "                    while Q:\n",
    "                        d, x, y = Q.popleft() \n",
    "                        for [nx, ny] in [[x+1, y], [x-1, y], [x, y+1], [x, y-1]]:\n",
    "                            if 0<=nx<m and 0<=ny< n and grid[nx][ny] == 0 and not vis[nx][ny]:\n",
    "                                vis[nx][ny] = 1\n",
    "                                D[nx][ny] += d+1\n",
    "                                cnt_from[nx][ny] += 1\n",
    "                                Q.append((d+1, nx, ny)) \n",
    "        ans = float('inf')\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0 and cnt_from[i][j] == cnt:\n",
    "                    ans = min(ans, D[i][j]) \n",
    "        return ans if 0< ans < float('inf')  else -1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestDistance(self, grid: List[List[int]]) -> int:\n",
    "        \"\"\"\n",
    "        思路：用一个matrix作为记录记录，记录0节点：能够到达该0节点的1的个数；达到该0节点的1的距离和。\n",
    "        然后遍历matrix矩阵，当几点0的到达该节点1的个数和总的1的个数相同时，就求最小和\n",
    "        \"\"\"\n",
    "        def dfs(i, j):\n",
    "            dq = []\n",
    "            dq.append((i, j, 0))\n",
    "            tmp = copy.deepcopy(grid)\n",
    "            while dq:\n",
    "                i, j, level = dq.pop(0)\n",
    "                for i, j in [[i, j + 1], [i, j - 1], [i + 1, j], [i - 1, j]]:\n",
    "                    if 0 <= i < m and 0 <= j < n and tmp[i][j] == 0:\n",
    "                        tmp[i][j] = level + 1\n",
    "                        cunt_from_1[i][j] += 1\n",
    "                        sum_from_1[i][j] += (level + 1)\n",
    "                        dq.append((i, j, level + 1))\n",
    "\n",
    "        # 剪枝\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        if m == 1 and n == 1:\n",
    "            return -1\n",
    "\n",
    "        cunt_from_1 = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        sum_from_1 = copy.deepcopy(cunt_from_1)\n",
    "        cunt_1 = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    cunt_1 += 1\n",
    "                    dfs(i, j)\n",
    "\n",
    "        res = float('inf')\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0 and cunt_from_1[i][j] == cunt_1:\n",
    "                    res = min(res, sum_from_1[i][j])\n",
    "        return res if res != float('inf') else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestDistance(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "\n",
    "        numOf1=[[0 for _ in range(n)] for _ in range(m)]\n",
    "        disFrom1=[ [0 for _ in range(n)] for _ in range(m)]\n",
    "        cnt1=0\n",
    "\n",
    "        for r in range(m):\n",
    "            for c in range(n):\n",
    "                if grid[r][c]==1:\n",
    "                    cnt1+=1\n",
    "                    queue = []\n",
    "                    queue.append((r,c,0))\n",
    "                    vst = [ [False for _ in range(n)] for _ in range(m)]\n",
    "                    while queue:\n",
    "                        i,j,d = queue.pop(0)\n",
    "                        for ni,nj in ((i-1,j),(i+1,j),(i,j-1),(i,j+1)):\n",
    "                            if 0<=ni<m and 0<=nj<n and grid[ni][nj]==0 and vst[ni][nj]==False:\n",
    "                                numOf1[ni][nj]+=1\n",
    "                                disFrom1[ni][nj]+=d+1\n",
    "                                queue.append((ni,nj,d+1))\n",
    "                                vst[ni][nj]=True\n",
    "        res = math.inf\n",
    "        for r in range(m):\n",
    "            for c in range(n):\n",
    "                if grid[r][c]==0:\n",
    "                    if numOf1[r][c]==cnt1:\n",
    "                        res = min(res,disFrom1[r][c])\n",
    "        return res if res!=math.inf else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestDistance(self, grid: List[List[int]]) -> int:\n",
    "        if not grid: return -1\n",
    "        m,n = len(grid), len(grid[0])\n",
    "        mark, res = 0, inf\n",
    "        curDistance = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        accumDistance = [[0 for _ in range(n)] for _ in range(m)]\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    self.bfs(grid, i, j, mark, curDistance, accumDistance)\n",
    "                    mark -= 1\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == mark:\n",
    "                    res = min(res, accumDistance[i][j])\n",
    "        return res if res != inf else -1\n",
    "    \n",
    "    def bfs(self, grid, i, j, mark, curDistance, accumDistance):\n",
    "        q = collections.deque([(i,j)])\n",
    "        dirs = [[0, 1], [-1, 0], [0, -1], [1, 0]]\n",
    "        distance = 1\n",
    "        while q:\n",
    "            le = len(q)\n",
    "            for _ in range(le):\n",
    "                x, y = q.popleft()\n",
    "                for dx,dy in dirs:\n",
    "                    nx, ny = x + dx, y + dy \n",
    "                    if 0 <= nx < len(grid) and 0 <= ny < len(grid[0]) and grid[nx][ny] == mark:\n",
    "                        grid[nx][ny] -= 1\n",
    "                        q.append((nx, ny))\n",
    "                        curDistance[nx][ny] = distance\n",
    "                        accumDistance[nx][ny] += curDistance[nx][ny]\n",
    "            distance += 1\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reachout(self, dist, i, j, num_building, grid):\n",
    "        M, N = len(grid), len(grid[0])\n",
    "        direct = [[-1,0], [0,-1], [0,1], [1,0]]\n",
    "        flag = False\n",
    "        step = 0\n",
    "        parents = [[i,j]]\n",
    "        while parents:\n",
    "            children = []\n",
    "            step += 1\n",
    "            for pa in parents:\n",
    "                for di in direct:\n",
    "                    ch = [pa[0]+di[0], pa[1]+di[1]]\n",
    "                    if ch[0]>=0 and ch[0]<M and ch[1]>=0 and ch[1]<N and grid[ch[0]][ch[1]]==0 and dist[ch[0]][ch[1]][0]==num_building:\n",
    "                        dist[ch[0]][ch[1]][0] += 1\n",
    "                        dist[ch[0]][ch[1]][1] += step\n",
    "                        flag = True\n",
    "                        children.append(ch)\n",
    "            parents = children\n",
    "        return flag\n",
    "\n",
    "\n",
    "    def shortestDistance(self, grid: List[List[int]]) -> int:\n",
    "        M, N = len(grid), len(grid[0])\n",
    "        dist = [[[0,0] for _ in range(N)] for _ in range(M)]\n",
    "        num_building = 0\n",
    "        for i in range(M):\n",
    "            for j in range(N):\n",
    "                if grid[i][j] == 1:\n",
    "                    flag = self.reachout(dist, i, j, num_building, grid)\n",
    "                    num_building += 1\n",
    "                    if not flag:\n",
    "                        return -1\n",
    "\n",
    "        return min(dist[i][j][1] for i in range(M) for j in range(N) if dist[i][j][0]==num_building)       \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestDistance(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        total_dist = [[0]* n for _ in range(m)]\n",
    "        min_dist = float('inf')\n",
    "        building_count = 0\n",
    "        mark = 0\n",
    "        dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]\n",
    "        \n",
    "        def helper(row, col, mark):\n",
    "            queue = deque([(i, j, 0)])\n",
    "            while queue:\n",
    "                x, y, dist = queue.popleft()\n",
    "                for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:\n",
    "                    nx, ny = x + dx, y + dy\n",
    "                    if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == mark:\n",
    "                        total_dist[nx][ny] += dist + 1\n",
    "                        queue.append((nx, ny, dist + 1))\n",
    "                        grid[nx][ny] -= 1\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    helper(i, j, mark)\n",
    "                    mark -= 1\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == mark:\n",
    "                    min_dist = min(min_dist, total_dist[i][j])\n",
    "        \n",
    "        return min_dist if min_dist != float('inf') else -1\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestDistance(self, grid: List[List[int]]) -> int:\n",
    "        Row, Col = len(grid), len(grid[0])\n",
    "\n",
    "        canget_from_1 = [[0 for _ in range(Col)] for _ in range(Row)]  #空地，有多少个建筑物可以到达\n",
    "        dist_sum_from_1 = [[0 for _ in range(Col)] for _ in range(Row)]    #空地， 可以到达的建筑物们的距离和\n",
    "        cnt_1 = 0           #建筑物1的数量\n",
    "        for r in range(Row):\n",
    "            for c in range(Col):\n",
    "                if grid[r][c] == 1:\n",
    "                    cnt_1 += 1\n",
    "                    Q = []\n",
    "                    Q.append((r, c, 0))\n",
    "                    visited = [[False for _ in range(Col)] for _ in range(Row)]\n",
    "                    while Q:\n",
    "                        i, j, d = Q.pop(0)\n",
    "                        for ni, nj in ((i-1,j), (i+1,j), (i,j-1), (i,j+1)):\n",
    "                            if (0 <= ni < Row) and (0 <= nj < Col) and (grid[ni][nj] == 0) and (visited[ni][nj] == False):\n",
    "                                canget_from_1[ni][nj] += 1\n",
    "                                dist_sum_from_1[ni][nj] += (d + 1)\n",
    "                                Q.append((ni, nj, d + 1))\n",
    "                                visited[ni][nj] = True\n",
    "        res = float('inf')\n",
    "        for r in range(Row):\n",
    "            for c in range(Col):\n",
    "                if grid[r][c] == 0:\n",
    "                    if canget_from_1[r][c] == cnt_1:\n",
    "                        res = min(res, dist_sum_from_1[r][c])\n",
    "        return res if res != float('inf') else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestDistance(self, grid: List[List[int]]) -> int:\n",
    "        row, col = len(grid), len(grid[0])\n",
    "        canget_from_1 = [[0 for _ in range(col)] for _ in range (row)]\n",
    "        dist_sum_from_1 = [[0 for _ in range(col)] for _ in range (row)]\n",
    "        cnt = 0\n",
    "        for r in range(row):\n",
    "            for c in range(col):\n",
    "                if grid[r][c]==1:\n",
    "                    cnt += 1\n",
    "                    Q = deque()\n",
    "                    Q.append((r,c,0))\n",
    "                    visited = [[False for _ in range(col)] for _ in range(row)]\n",
    "                    while Q:\n",
    "                        i,j,count = Q.popleft()\n",
    "                        for ni,nj in [(i+1,j), (i-1,j), (i,j+1), (i,j-1)]:\n",
    "                            if 0<=ni<row and 0 <= nj <col and visited[ni][nj] == False and grid[ni][nj] ==0:\n",
    "                                canget_from_1[ni][nj] += 1\n",
    "                                dist_sum_from_1[ni][nj] += (count+1)\n",
    "                                Q.append((ni,nj,count+1))\n",
    "                                visited[ni][nj] = True\n",
    "        res = float('inf')\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if grid[i][j] == 0 and canget_from_1[i][j] == cnt:\n",
    "                    res = min(res, dist_sum_from_1[i][j])\n",
    "        return res if res != float('inf') else -1\n",
    "\n",
    "\n",
    "                        \n",
    "\n",
    "        \n",
    "        \n",
    "        # Row, Col = len(grid), len(grid[0])\n",
    "\n",
    "        # canget_from_1 = [[0 for _ in range(Col)] for _ in range(Row)]  #空地，有多少个建筑物可以到达\n",
    "        # dist_sum_from_1 = [[0 for _ in range(Col)] for _ in range(Row)]    #空地， 可以到达的建筑物们的距离和\n",
    "        # cnt_1 = 0           #建筑物1的数量\n",
    "        # for r in range(Row):\n",
    "        #     for c in range(Col):\n",
    "        #         if grid[r][c] == 1:\n",
    "        #             cnt_1 += 1\n",
    "        #             Q = []\n",
    "        #             Q.append((r, c, 0))\n",
    "        #             visited = [[False for _ in range(Col)] for _ in range(Row)]\n",
    "        #             while Q:\n",
    "        #                 i, j, d = Q.pop(0)\n",
    "        #                 for ni, nj in ((i-1,j), (i+1,j), (i,j-1), (i,j+1)):\n",
    "        #                     if (0 <= ni < Row) and (0 <= nj < Col) and (grid[ni][nj] == 0) and (visited[ni][nj] == False):\n",
    "        #                         canget_from_1[ni][nj] += 1\n",
    "        #                         dist_sum_from_1[ni][nj] += (d + 1)\n",
    "        #                         Q.append((ni, nj, d + 1))\n",
    "        #                         visited[ni][nj] = True\n",
    "\n",
    "        # res = float('inf')\n",
    "        # for r in range(Row):\n",
    "        #     for c in range(Col):\n",
    "        #         if grid[r][c] == 0:\n",
    "        #             if canget_from_1[r][c] == cnt_1:\n",
    "        #                 res = min(res, dist_sum_from_1[r][c])\n",
    "        # return res if res != float('inf') else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestDistance(self, grid: List[List[int]]) -> int:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        \n",
    "        canget = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        dist = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        \n",
    "        cnt_1 =0\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    cnt_1 +=1\n",
    "                    q =[]\n",
    "                    q.append((i,j,0))\n",
    "                    visited = [[False for _ in range(n)] for _ in range(m)]\n",
    "\n",
    "                    while q:\n",
    "                        x,y,d = q.pop(0)\n",
    "                        for nx,ny in [(x+1,y),(x,y+1),(x-1,y),(x,y-1)]:\n",
    "                            if 0<=nx<m and 0<=ny<n and grid[nx][ny]==0 and  visited[nx][ny]==False:\n",
    "                                visited[nx][ny] = True\n",
    "                                canget[nx][ny] +=1\n",
    "                                dist[nx][ny] += (d+1)\n",
    "                                q.append((nx,ny,d+1))\n",
    "                        \n",
    "\n",
    "        res = float('inf')\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0 and canget[i][j] == cnt_1:\n",
    "                    res = min(res,dist[i][j])\n",
    "        \n",
    "        return res if res != float('inf') else -1\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestDistance(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        ans = float('inf')\n",
    "        disRecord = [[0 for y in range(n)] for x in range(m)]\n",
    "        buildCount = 0\n",
    "        visRecord = [[0 for y in range(n)] for x in range(m)]\n",
    "        def bfs(i, j):\n",
    "            visited = [[True for y in range(n)] for x in range(m)]\n",
    "            visited[i][j] = False \n",
    "            queue = deque()\n",
    "            queue.append([i, j])\n",
    "            step = 1\n",
    "            totalBank = 0\n",
    "            while queue:\n",
    "                for _ in range(len(queue)):\n",
    "                    x, y = queue.pop()\n",
    "                    for i, j in [[x+1, y], [x-1, y], [x, y+1], [x, y-1]]:\n",
    "                        if not(0<=i<m and 0<=j<n) or grid[i][j] != 0 or visited[i][j] is False:\n",
    "                            continue\n",
    "                        visited[i][j] = False \n",
    "\n",
    "                        if grid[i][j] == 0:\n",
    "                            visRecord[i][j] += 1\n",
    "                            disRecord[i][j] += step \n",
    "                            totalBank += 1\n",
    "                        queue.appendleft([i, j])\n",
    "                step += 1\n",
    "            return totalBank == 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    buildCount += 1\n",
    "                    if bfs(i, j):\n",
    "                        return -1\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if visRecord[i][j] == buildCount and grid[i][j] == 0:\n",
    "                    ans = min(ans, disRecord[i][j])\n",
    "        return ans if ans != float('inf') else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestDistance(self, grid: List[List[int]]) -> int:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        \n",
    "        canget = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        dist = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        \n",
    "        cnt_1 =0\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    cnt_1 +=1\n",
    "                    q =[]\n",
    "                    q.append((i,j,0))\n",
    "                    visited = [[False for _ in range(n)] for _ in range(m)]\n",
    "\n",
    "                    while q:\n",
    "                        x,y,d = q.pop(0)\n",
    "                        for nx,ny in [(x+1,y),(x,y+1),(x-1,y),(x,y-1)]:\n",
    "                            if 0<=nx<m and 0<=ny<n and grid[nx][ny]==0 and  visited[nx][ny]==False:\n",
    "                                visited[nx][ny] = True\n",
    "                                canget[nx][ny] +=1\n",
    "                                dist[nx][ny] += (d+1)\n",
    "                                q.append((nx,ny,d+1))\n",
    "                        \n",
    "\n",
    "        res = float('inf')\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0 and canget[i][j] == cnt_1:\n",
    "                    res = min(res,dist[i][j])\n",
    "        \n",
    "        return res if res != float('inf') else -1\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestDistance(self, grid: List[List[int]]) -> int:\n",
    "        Row, Col = len(grid), len(grid[0])\n",
    "\n",
    "        canget_from_1 = [[0 for _ in range(Col)] for _ in range(Row)]  #空地，有多少个建筑物可以到达\n",
    "        dist_sum_from_1 = [[0 for _ in range(Col)] for _ in range(Row)]    #空地， 可以到达的建筑物们的距离和\n",
    "        cnt_1 = 0           #建筑物1的数量\n",
    "        for r in range(Row):\n",
    "            for c in range(Col):\n",
    "                if grid[r][c] == 1:\n",
    "                    cnt_1 += 1\n",
    "                    Q = []\n",
    "                    Q.append((r, c, 0))\n",
    "                    visited = [[False for _ in range(Col)] for _ in range(Row)]\n",
    "                    while Q:\n",
    "                        i, j, d = Q.pop(0)\n",
    "                        for ni, nj in ((i-1,j), (i+1,j), (i,j-1), (i,j+1)):\n",
    "                            if (0 <= ni < Row) and (0 <= nj < Col) and (grid[ni][nj] == 0) and (visited[ni][nj] == False):\n",
    "                                canget_from_1[ni][nj] += 1\n",
    "                                dist_sum_from_1[ni][nj] += (d + 1)\n",
    "                                Q.append((ni, nj, d + 1))\n",
    "                                visited[ni][nj] = True\n",
    "        res = float('inf')\n",
    "        for r in range(Row):\n",
    "            for c in range(Col):\n",
    "                if grid[r][c] == 0:\n",
    "                    if canget_from_1[r][c] == cnt_1:\n",
    "                        res = min(res, dist_sum_from_1[r][c])\n",
    "        return res if res != float('inf') else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestDistance(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dis = [[0] * n for _ in range(m)]\n",
    "        cnt = [[0] * n for _ in range(m)]\n",
    "\n",
    "        def bfs(node):\n",
    "            visit = [[0] * n for _ in range(m)]\n",
    "            stack = [node]\n",
    "            step = 1\n",
    "            while stack:\n",
    "                nex = []\n",
    "                for i, j in stack:\n",
    "                    for node in [[i + 1, j], [i - 1, j], [i, j - 1], [i, j + 1]]:\n",
    "                        if 0 <= node[0] < m and 0 <= node[1] < n and not grid[node[0]][node[1]] and not visit[node[0]][node[1]]:\n",
    "                            nex.append(node)\n",
    "                            visit[node[0]][node[1]] = 1\n",
    "                            dis[node[0]][node[1]] += step\n",
    "                            cnt[node[0]][node[1]] += 1\n",
    "                stack = nex[:]\n",
    "                step += 1\n",
    "            return\n",
    "\n",
    "        count = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    bfs([i, j])\n",
    "                    count += 1\n",
    "\n",
    "        ans = float('inf')\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if not grid[i][j] and dis[i][j] and cnt[i][j]==count:\n",
    "                    if dis[i][j] < ans:\n",
    "                        ans = dis[i][j]\n",
    "\n",
    "        return -1 if ans == float('inf') else ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def shortestDistance(self, grid: List[List[int]]) -> int:\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        buidcount=[[0]*n for _ in range(m)]\n",
    "        buildis=[[0]*n for _ in range(m)]\n",
    "        cnt=0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==1:\n",
    "                    cnt+=1\n",
    "                    stack=collections.deque()\n",
    "                    stack.append([i,j,0])\n",
    "                    vis=[[False]*n for _ in range(m)]\n",
    "                    while stack:\n",
    "                        x,y,d =stack.popleft()\n",
    "                        #if vis[x][y]==True:\n",
    "                       #     continue\n",
    "                       # vis[x][y]=True\n",
    "                        for x1,y1 in [[x+1,y],[x-1,y],[x,y+1],[x,y-1]]:\n",
    "                            if 0<=x1<m and 0<=y1<n and grid[x1][y1]==0 and vis[x1][y1]==False:\n",
    "                                buidcount[x1][y1]+=1\n",
    "                                buildis[x1][y1]+=d+1\n",
    "                                stack.append([x1,y1,d+1])\n",
    "                                vis[x1][y1]=True\n",
    "        res=float(\"inf\")\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==0 and buidcount[i][j]==cnt:\n",
    "                    res=min(res,buildis[i][j])\n",
    "        if res==float(\"inf\"):\n",
    "            return -1\n",
    "        else:\n",
    "            return res \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestDistance(self, grid: List[List[int]]) -> int:\n",
    "        # 计算从每个建筑物到每个空地的距离, 再对空地进行统计, 所有建筑物都能到达的空地中, 距离最小的那个即为所求. \n",
    "        # 1. 我们需要dist记录本次BFS中距离建筑物的距离, sum记录总的距离，res为最短的距离和（初始化为INT_MAX）. \n",
    "        # 2. 因为空地需要到达所有的建筑物, 使用grid矩阵去记录当前空地被访问了多少次, times变量记录进行了多少次BFS. 为了和0/1/2的意义区分，times初始化为0，之后递减。\n",
    "        # 3. 只有当这个空地的grid值和的times相等时, 证明之前BFS中我们都访问过这个空地，这次才继续访问这个空地. \n",
    "        # 4. 访问时，递减grid的值，更新dist, sum，和res。如果当前一轮BFS结束，res仍然为INT_MAX,那么说明无解。\n",
    "        int_max = 2 ** 31 - 1\n",
    "        res = int_max\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        times = 0\n",
    "        dist = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        m_sum = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]\n",
    "\n",
    "        queue = collections.deque()\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    # 遍历所有的建筑物, 作为起点进行BFS\n",
    "                    res = int_max\n",
    "                    queue.append([i, j])\n",
    "                    while len(queue) != 0:\n",
    "                        cur_x, cur_y = queue.popleft()\n",
    "                        for x_offset, y_offset in directions:\n",
    "                            x, y = cur_x + x_offset, cur_y + y_offset\n",
    "                            if x >= 0 and x < m and y >= 0 and y < n and grid[x][y] == times:\n",
    "                                # 如果没有越界, 而且是之前的|times|次BFS都被遍历到的节点\n",
    "                                grid[x][y] -= 1\n",
    "                                # 计算本次BFS中距离建筑物的距离\n",
    "                                dist[x][y] = dist[cur_x][cur_y] + 1\n",
    "                                # 更新所有建筑物到该空地的距离\n",
    "                                m_sum[x][y] += dist[x][y]\n",
    "                                res = min(res, m_sum[x][y])\n",
    "                                queue.append([x, y])\n",
    "                    if res == int_max:\n",
    "                        # 说明不存在一个空地, 可以到达之前的所有建筑物, 直接返回-1\n",
    "                        return -1\n",
    "                    # 更新BFS次数\n",
    "                    times -= 1\n",
    "        return res\n",
    "\n",
    "# 作者：extra101\n",
    "# 链接：https://leetcode.cn/problems/shortest-distance-from-all-buildings/solutions/952981/python-by-extra101-ayv9/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestDistance(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        result = [[float(\"inf\") if grid[i][j] != 0 else 0 for j in range(n)] for i in range(m)]\n",
    "        d = [[float(\"inf\")]*n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] != 1: continue\n",
    "                d[i][j] = 0\n",
    "                queue = collections.deque([(i, j)])\n",
    "                while queue:\n",
    "                    x, y = queue.popleft()\n",
    "                    step = d[x][y]\n",
    "                    for dx, dy in ((-1, 0), (1, 0), (0, -1), (0, 1)):\n",
    "                        if 0<=x+dx<m and 0<=y+dy<n and grid[x+dx][y+dy] == 0:\n",
    "                            if step+1<d[x+dx][y+dy]:\n",
    "                                d[x+dx][y+dy]=step+1\n",
    "                                queue.append((x+dx, y+dy))\n",
    "                for ii in range(m):\n",
    "                    for jj in range(n):\n",
    "                        result[ii][jj] += d[ii][jj]\n",
    "                        d[ii][jj] = float(\"inf\")\n",
    "        mlen = min(map(min, result))\n",
    "        return -1 if mlen == float(\"inf\") else mlen"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestDistance(self, grid: List[List[int]]) -> int:\n",
    "        # 计算从每个建筑物到每个空地的距离, 再对空地进行统计, 所有建筑物都能到达的空地中, 距离最小的那个即为所求. \n",
    "        # 1. 我们需要dist记录本次BFS中距离建筑物的距离, sum记录总的距离，res为最短的距离和（初始化为INT_MAX）. \n",
    "        # 2. 因为空地需要到达所有的建筑物, 使用grid矩阵去记录当前空地被访问了多少次, times变量记录进行了多少次BFS. 为了和0/1/2的意义区分，times初始化为0，之后递减。\n",
    "        # 3. 只有当这个空地的grid值和的times相等时, 证明之前BFS中我们都访问过这个空地，这次才继续访问这个空地. \n",
    "        # 4. 访问时，递减grid的值，更新dist, sum，和res。如果当前一轮BFS结束，res仍然为INT_MAX,那么说明无解。\n",
    "        int_max = 2 ** 31 - 1\n",
    "        res = int_max\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        times = 0\n",
    "        dist = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        m_sum = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]\n",
    "\n",
    "        queue = collections.deque()\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    # 遍历所有的建筑物, 作为起点进行BFS\n",
    "                    res = int_max\n",
    "                    queue.append([i, j])\n",
    "                    while len(queue) != 0:\n",
    "                        cur_x, cur_y = queue.popleft()\n",
    "                        for x_offset, y_offset in directions:\n",
    "                            x, y = cur_x + x_offset, cur_y + y_offset\n",
    "                            if x >= 0 and x < m and y >= 0 and y < n and grid[x][y] == times:\n",
    "                                # 如果没有越界, 而且是之前的|times|次BFS都被遍历到的节点\n",
    "                                grid[x][y] -= 1\n",
    "                                # 计算本次BFS中距离建筑物的距离\n",
    "                                dist[x][y] = dist[cur_x][cur_y] + 1\n",
    "                                # 更新所有建筑物到该空地的距离\n",
    "                                m_sum[x][y] += dist[x][y]\n",
    "                                res = min(res, m_sum[x][y])\n",
    "                                queue.append([x, y])\n",
    "                    if res == int_max:\n",
    "                        # 说明不存在一个空地, 可以到达之前的所有建筑物, 直接返回-1\n",
    "                        return -1\n",
    "                    # 更新BFS次数\n",
    "                    times -= 1\n",
    "        return res\n",
    "\n",
    "# 作者：extra101\n",
    "# 链接：https://leetcode.cn/problems/shortest-distance-from-all-buildings/solutions/952981/python-by-extra101-ayv9/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def shortestDistance(self, grid: List[List[int]]) -> int:\n",
    "        \"\"\"\n",
    "        思路：用一个matrix作为记录记录，记录0节点：能够到达该0节点的1的个数；达到该0节点的1的距离和。\n",
    "        然后遍历matrix矩阵，当几点0的到达该节点1的个数和总的1的个数相同时，就求最小和\n",
    "        \"\"\"\n",
    "        def dfs(i, j):\n",
    "            dq = []\n",
    "            dq.append((i, j, 0))\n",
    "            tmp = copy.deepcopy(grid)\n",
    "            while dq:\n",
    "                i, j, level = dq.pop(0)\n",
    "                for i, j in [[i, j + 1], [i, j - 1], [i + 1, j], [i - 1, j]]:\n",
    "                    if 0 <= i < m and 0 <= j < n and tmp[i][j] == 0:\n",
    "                        tmp[i][j] = level + 1\n",
    "                        matrix[i][j][0] += 1\n",
    "                        matrix[i][j][1] += (level + 1)\n",
    "                        dq.append((i, j, level + 1))\n",
    "\n",
    "        # 剪枝\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        if m == 1 and n == 1:\n",
    "            return -1\n",
    "\n",
    "        matrix = [[[0, 0] for _ in range(n)] for _ in range(m)]\n",
    "        cunt_1 = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    cunt_1 += 1\n",
    "                    dfs(i, j)\n",
    "\n",
    "        res = float('inf')\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0 and matrix[i][j][0] == cunt_1:\n",
    "                    res = min(res, matrix[i][j][1])\n",
    "        return res if res != float('inf') else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestDistance(self, grid: List[List[int]]) -> int:\n",
    "        Row, Col = len(grid), len(grid[0])\n",
    "\n",
    "        canget_from_1 = [[0 for _ in range(Col)] for _ in range(Row)]  #空地，有多少个建筑物可以到达\n",
    "        dist_sum_from_1 = [[0 for _ in range(Col)] for _ in range(Row)]    #空地， 可以到达的建筑物们的距离和\n",
    "        cnt_1 = 0           #建筑物1的数量\n",
    "        for r in range(Row):\n",
    "            for c in range(Col):\n",
    "                if grid[r][c] == 1:\n",
    "                    cnt_1 += 1\n",
    "                    Q = []\n",
    "                    Q.append((r, c, 0))\n",
    "                    visited = [[False for _ in range(Col)] for _ in range(Row)]\n",
    "                    while Q:\n",
    "                        i, j, d = Q.pop(0)\n",
    "                        for ni, nj in ((i-1,j), (i+1,j), (i,j-1), (i,j+1)):\n",
    "                            if (0 <= ni < Row) and (0 <= nj < Col) and (grid[ni][nj] == 0) and (visited[ni][nj] == False):\n",
    "                                canget_from_1[ni][nj] += 1\n",
    "                                dist_sum_from_1[ni][nj] += (d + 1)\n",
    "                                Q.append((ni, nj, d + 1))\n",
    "                                visited[ni][nj] = True\n",
    "        res = float('inf')\n",
    "        for r in range(Row):\n",
    "            for c in range(Col):\n",
    "                if grid[r][c] == 0:\n",
    "                    if canget_from_1[r][c] == cnt_1:\n",
    "                        res = min(res, dist_sum_from_1[r][c])\n",
    "        return res if res != float('inf') else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestDistance(self, grid: List[List[int]]) -> int:\n",
    "        # 计算从每个建筑物到每个空地的距离, 再对空地进行统计, 所有建筑物都能到达的空地中, 距离最小的那个即为所求. 1. 我们需要dist记录本次BFS中距离建筑物的距离, sum记录总的距离，res为最短的距离和（初始化为INT_MAX）. 2. 因为空地需要到达所有的建筑物, 使用grid矩阵去记录当前空地被访问了多少次, times变量记录进行了多少次BFS. 为了和0/1/2的意义区分，times初始化为0，之后递减。3. 只有当这个空地的grid值和的times相等时, 证明之前BFS中我们都访问过这个空地，这次才继续访问这个空地. 4. 访问时，递减grid的值，更新dist, sum，和res。如果当前一轮BFS结束，res仍然为INT_MAX,那么说明无解。\n",
    "        int_max = 2 ** 31 - 1\n",
    "        res = int_max\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        times = 0\n",
    "        dist = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        m_sum = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]\n",
    "\n",
    "        queue = collections.deque()\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    # 遍历所有的建筑物, 作为起点进行BFS\n",
    "                    res = int_max\n",
    "                    queue.append([i, j])\n",
    "                    while len(queue) != 0:\n",
    "                        cur_x, cur_y = queue.popleft()\n",
    "                        for x_offset, y_offset in directions:\n",
    "                            x, y = cur_x + x_offset, cur_y + y_offset\n",
    "                            if x >= 0 and x < m and y >= 0 and y < n and grid[x][y] == times:\n",
    "                                # 如果没有越界, 而且是之前的|times|次BFS都被遍历到的节点\n",
    "                                grid[x][y] -= 1\n",
    "                                # 计算本次BFS中距离建筑物的距离\n",
    "                                dist[x][y] = dist[cur_x][cur_y] + 1\n",
    "                                # 更新所有建筑物到该空地的距离\n",
    "                                m_sum[x][y] += dist[x][y]\n",
    "                                res = min(res, m_sum[x][y])\n",
    "                                queue.append([x, y])\n",
    "                    if res == int_max:\n",
    "                        # 说明不存在一个空地, 可以到达之前的所有建筑物, 直接返回-1\n",
    "                        return -1\n",
    "                    # 更新BFS次数\n",
    "                    times -= 1\n",
    "        return res\n",
    "\n",
    "# 作者：extra101\n",
    "# 链接：https://leetcode.cn/problems/shortest-distance-from-all-buildings/solutions/952981/python-by-extra101-ayv9/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestDistance(self, grid: List[List[int]]) -> int:\n",
    "        Row, Col = len(grid), len(grid[0])\n",
    "\n",
    "        canget_from_1 = [[0 for _ in range(Col)] for _ in range(Row)]  #空地，有多少个建筑物可以到达\n",
    "        dist_sum_from_1 = [[0 for _ in range(Col)] for _ in range(Row)]    #空地， 可以到达的建筑物们的距离和\n",
    "        cnt_1 = 0           #建筑物1的数量\n",
    "        for r in range(Row):\n",
    "            for c in range(Col):\n",
    "                if grid[r][c] == 1:\n",
    "                    cnt_1 += 1\n",
    "                    Q = []\n",
    "                    Q.append((r, c, 0))\n",
    "                    visited = [[False for _ in range(Col)] for _ in range(Row)]\n",
    "                    while Q:\n",
    "                        i, j, d = Q.pop(0)\n",
    "                        for ni, nj in ((i-1,j), (i+1,j), (i,j-1), (i,j+1)):\n",
    "                            if (0 <= ni < Row) and (0 <= nj < Col) and (grid[ni][nj] == 0) and (visited[ni][nj] == False):\n",
    "                                canget_from_1[ni][nj] += 1\n",
    "                                dist_sum_from_1[ni][nj] += (d + 1)\n",
    "                                Q.append((ni, nj, d + 1))\n",
    "                                visited[ni][nj] = True\n",
    "        res = float('inf')\n",
    "        for r in range(Row):\n",
    "            for c in range(Col):\n",
    "                if grid[r][c] == 0:\n",
    "                    if canget_from_1[r][c] == cnt_1:\n",
    "                        res = min(res, dist_sum_from_1[r][c])\n",
    "        return res if res != float('inf') else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestDistance(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "\n",
    "        n, m = len(grid), len(grid[0])\n",
    "\n",
    "        distances = [[[0, 0] for _ in range(m)] for i in range(n)]\n",
    "        #distances[i][j][0] -> 可以到达多少个建筑物，[1] 可以到达的建筑物的距离和\n",
    "        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]\n",
    "        buildingCount = 0\n",
    "        for i in range(n):\n",
    "\n",
    "            for j in range(m):\n",
    "\n",
    "                if grid[i][j] == 1:\n",
    "                    buildingCount += 1\n",
    "                    Q = collections.deque([(i, j, 0)])\n",
    "                    visited = [[False] * (m) for i in range(n)]\n",
    "                    while Q:\n",
    "                        x, y, d = Q.popleft()\n",
    "                        for dx, dy in directions:\n",
    "                            nx, ny = x + dx, y + dy\n",
    "                            if 0 <= nx < n and 0 <= ny < m and grid[nx][ny] == 0 and not visited[nx][ny]:\n",
    "\n",
    "                                distances[nx][ny][0] += 1\n",
    "                                distances[nx][ny][1] += d + 1\n",
    "                                Q.append((nx, ny, d + 1))\n",
    "                                visited[nx][ny] = True\n",
    "        res = float(\"inf\")\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j] == 0 and distances[i][j][0] == buildingCount:\n",
    "                    res = min(res, distances[i][j][1])\n",
    "\n",
    "\n",
    "        return res if res != float(\"inf\") else -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestDistance(self, grid: List[List[int]]) -> int:\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        D = [[0] * m for _ in range(n)]\n",
    "        cnt = 0\n",
    "        cnt_from_1 = [[0] * m for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j] == 1:\n",
    "                    Q = []\n",
    "                    Q.append((i,j, 0))\n",
    "                    cnt += 1\n",
    "                    vis = [[0] * m for _ in range(n)]\n",
    "                    while Q:\n",
    "                        x, y, d = Q.pop(0)\n",
    "                        for nx, ny in [[x+1, y], [x-1,y], [x, y+1], [x, y-1]]:\n",
    "                            if 0<=nx<n and 0<=ny<m and grid[nx][ny] == 0:\n",
    "                                if vis[nx][ny] == 0:\n",
    "                                    vis[nx][ny] = 1 \n",
    "                                    D[nx][ny] += d + 1 \n",
    "                                    Q.append((nx, ny, d+1)) \n",
    "                                    cnt_from_1[nx][ny] += 1\n",
    "        ans = float('inf') \n",
    "    \n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j] == 0 and cnt_from_1[i][j] == cnt:\n",
    "                    ans = min(ans, D[i][j]) \n",
    " \n",
    "        return ans if ans < float('inf') else -1\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution: \n",
    "    def shortestDistance(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        count_house = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    count_house += 1\n",
    "\n",
    "        dist = [[0] * n for _ in range(m)]\n",
    "        reach = [[0] * n for _ in range(m)]\n",
    "\n",
    "        def bfs(i, j): #from 1->\n",
    "            visit = set()\n",
    "            queue = collections.deque()\n",
    "            queue.append((i, j, 0))\n",
    "            visit.add((i, j))\n",
    "            count = 1\n",
    "            while queue:\n",
    "                i, j, step = queue.popleft()\n",
    "                for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:\n",
    "                    x = i + dx\n",
    "                    y = j + dy\n",
    "                    if 0 <= x < m and 0 <= y < n and (x, y) not in visit:\n",
    "                        if grid[x][y] == 0:                          \n",
    "                            reach[x][y] += 1 # these 2 lines under grid[x][y]==0 not == 1\n",
    "                            dist[x][y]+= step + 1 \n",
    "                            queue.append((x, y, step + 1))\n",
    "                        if grid[x][y] == 1:\n",
    "                            count += 1\n",
    "                        visit.add((x, y)) # 0, 1, or 2     \n",
    "            return count == count_house\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    if not bfs(i, j):\n",
    "                        return -1\n",
    "        # from here, move to be parallel to bfs\n",
    "        res = float('inf')\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] ==0 and reach[i][j]== count_house: # this line\n",
    "                    res = min(res, dist[i][j])\n",
    "        return res if res != float('inf') else -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def shortestDistance(self, grid: List[List[int]]) -> int:\n",
    "        \"\"\"\n",
    "        思路：用一个matrix作为记录记录，记录0节点：能够到达该0节点的1的个数；达到该0节点的1的距离和。\n",
    "        然后遍历matrix矩阵，当几点0的到达该节点1的个数和总的1的个数相同时，就求最小和\n",
    "        \"\"\"\n",
    "        def dfs(i, j):\n",
    "            dq = []\n",
    "            dq.append((i, j, 0))\n",
    "            tmp = copy.deepcopy(grid)\n",
    "            while dq:\n",
    "                i, j, level = dq.pop(0)\n",
    "                for i, j in [[i, j + 1], [i, j - 1], [i + 1, j], [i - 1, j]]:\n",
    "                    if 0 <= i < m and 0 <= j < n and tmp[i][j] == 0:\n",
    "                        tmp[i][j] = level + 1\n",
    "                        matrix[i][j][0] += 1\n",
    "                        matrix[i][j][1] += (level + 1)\n",
    "                        dq.append((i, j, level + 1))\n",
    "\n",
    "        # 剪枝\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        if m == 1 and n == 1:\n",
    "            return -1\n",
    "\n",
    "        matrix = [[[0, 0] for _ in range(n)] for _ in range(m)]\n",
    "        cunt_1 = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    cunt_1 += 1\n",
    "                    dfs(i, j)\n",
    "\n",
    "        res = float('inf')\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0 and matrix[i][j][0] == cunt_1:\n",
    "                    res = min(res, matrix[i][j][1])\n",
    "        return res if res != float('inf') else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def shortestDistance(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        # 计算空地数量和建筑集合\n",
    "        spaceCount, houseSet = 0, set()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    spaceCount += 1\n",
    "                elif grid[i][j] == 1:\n",
    "                    houseSet.add((i, j))\n",
    "        houseCount = len(houseSet)\n",
    "        # 计算建筑到达各个空地的次数和最小距离和\n",
    "        cntMatrix, disMatrix = [[0] * n for _ in range(m)], [[0] * n for _ in range(m)]\n",
    "        for h in houseSet:\n",
    "            dq, visited = deque(), set()\n",
    "            dq.appendleft(h)\n",
    "            dis = 0\n",
    "            while dq:\n",
    "                dis += 1\n",
    "                size = len(dq)\n",
    "                for _ in range(size):\n",
    "                    cur = dq.pop()\n",
    "                    for dir in [(-1, 0), (1, 0), (0, -1), (0, 1)]:\n",
    "                        i = cur[0] + dir[0]\n",
    "                        j = cur[1] + dir[1]\n",
    "                        if 0 <= i < m and 0 <= j < n and grid[i][j] == 0 and (i, j) not in visited:\n",
    "                            visited.add((i, j))\n",
    "                            cntMatrix[i][j] += 1\n",
    "                            disMatrix[i][j] += dis\n",
    "                            dq.appendleft((i, j))\n",
    "        # 在所有建筑可达的空地中找到最小距离\n",
    "        ans = float('inf')\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if cntMatrix[i][j] == houseCount:\n",
    "                    ans = min(ans, disMatrix[i][j])\n",
    "        if ans == float('inf'):\n",
    "            return -1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestDistance(self, grid: List[List[int]]) -> int:\n",
    "        Row, Col = len(grid), len(grid[0])\n",
    "\n",
    "        canget_from_1 = [[0 for _ in range(Col)] for _ in range(Row)]  #空地，有多少个建筑物可以到达\n",
    "        dist_sum_from_1 = [[0 for _ in range(Col)] for _ in range(Row)]    #空地， 可以到达的建筑物们的距离和\n",
    "        cnt_1 = 0           #建筑物1的数量\n",
    "        for r in range(Row):\n",
    "            for c in range(Col):\n",
    "                if grid[r][c] == 1:\n",
    "                    cnt_1 += 1\n",
    "                    Q = []\n",
    "                    Q.append((r, c, 0))\n",
    "                    visited = [[False for _ in range(Col)] for _ in range(Row)]\n",
    "                    while Q:\n",
    "                        i, j, d = Q.pop(0)\n",
    "                        for ni, nj in ((i-1,j), (i+1,j), (i,j-1), (i,j+1)):\n",
    "                            if (0 <= ni < Row) and (0 <= nj < Col) and (grid[ni][nj] == 0) and (visited[ni][nj] == False):\n",
    "                                canget_from_1[ni][nj] += 1\n",
    "                                dist_sum_from_1[ni][nj] += (d + 1)\n",
    "                                Q.append((ni, nj, d + 1))\n",
    "                                visited[ni][nj] = True\n",
    "        res = float('inf')\n",
    "        for r in range(Row):\n",
    "            for c in range(Col):\n",
    "                if grid[r][c] == 0:\n",
    "                    if canget_from_1[r][c] == cnt_1:\n",
    "                        res = min(res, dist_sum_from_1[r][c])\n",
    "        return res if res != float('inf') else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestDistance(self, grid: List[List[int]]) -> int:\n",
    "        Row, Col = len(grid), len(grid[0])\n",
    "\n",
    "        canget_from_1 = [[0 for _ in range(Col)] for _ in range(Row)]  #空地，有多少个建筑物可以到达\n",
    "        dist_sum_from_1 = [[0 for _ in range(Col)] for _ in range(Row)]    #空地， 可以到达的建筑物们的距离和\n",
    "        cnt_1 = 0           #建筑物1的数量\n",
    "        for r in range(Row):\n",
    "            for c in range(Col):\n",
    "                if grid[r][c] == 1:\n",
    "                    cnt_1 += 1\n",
    "                    Q = []\n",
    "                    Q.append((r, c, 0))\n",
    "                    visited = [[False for _ in range(Col)] for _ in range(Row)]\n",
    "                    while Q:\n",
    "                        i, j, d = Q.pop(0)\n",
    "                        for ni, nj in ((i-1,j), (i+1,j), (i,j-1), (i,j+1)):\n",
    "                            if (0 <= ni < Row) and (0 <= nj < Col) and (grid[ni][nj] == 0) and (visited[ni][nj] == False):\n",
    "                                canget_from_1[ni][nj] += 1\n",
    "                                dist_sum_from_1[ni][nj] += (d + 1)\n",
    "                                Q.append((ni, nj, d + 1))\n",
    "                                visited[ni][nj] = True\n",
    "\n",
    "        res = float('inf')\n",
    "        for r in range(Row):\n",
    "            for c in range(Col):\n",
    "                if grid[r][c] == 0:\n",
    "                    if canget_from_1[r][c] == cnt_1:\n",
    "                        res = min(res, dist_sum_from_1[r][c])\n",
    "        return res if res != float('inf') else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def shortestDistance(self, grid: List[List[int]]) -> int:\n",
    "        \"\"\"\n",
    "        思路：用一个matrix作为记录记录，记录0节点：能够到达该0节点的1的个数；达到该0节点的1的距离和。\n",
    "        然后遍历matrix矩阵，当几点0的到达该节点1的个数和总的1的个数相同时，就求最小和\n",
    "        \"\"\"\n",
    "        def dfs(i, j):\n",
    "            dq = deque()\n",
    "            dq.append((i, j, 0))\n",
    "            tmp = copy.deepcopy(grid)\n",
    "            while dq:\n",
    "                i, j, level = dq.popleft()\n",
    "                for i, j in [[i, j + 1], [i, j - 1], [i + 1, j], [i - 1, j]]:\n",
    "                    if 0 <= i < m and 0 <= j < n and tmp[i][j] == 0:\n",
    "                        tmp[i][j] = level + 1\n",
    "                        matrix[i][j][0] += 1\n",
    "                        matrix[i][j][1] += (level + 1)\n",
    "                        dq.append((i, j, level + 1))\n",
    "\n",
    "        # 剪枝\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        if m == 1 and n == 1:\n",
    "            return -1\n",
    "\n",
    "        matrix = [[[0, 0] for _ in range(n)] for _ in range(m)]\n",
    "        cunt_1 = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    cunt_1 += 1\n",
    "                    dfs(i, j)\n",
    "\n",
    "        res = float('inf')\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0 and matrix[i][j][0] == cunt_1:\n",
    "                    res = min(res, matrix[i][j][1])\n",
    "        return res if res != float('inf') else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def shortestDistance(self, grid: List[List[int]]) -> int:\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        count=[[0 for _ in range(n)] for _ in range(m)]\n",
    "        distance=[[0 for _ in range(n)] for _ in range(m)]\n",
    "\n",
    "        # 首先以每个建筑进行bfs\n",
    "        starts=[]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==1:\n",
    "                    starts.append((i,j))\n",
    "\n",
    "        for start in starts:\n",
    "            queue=deque()\n",
    "            queue.append((start[0],start[1],0))\n",
    "            visited=set()\n",
    "            visited.add(start)\n",
    "            while queue:\n",
    "                x,y,d=queue.popleft()\n",
    "                neis=((x+1,y),(x-1,y),(x,y+1),(x,y-1))\n",
    "                for nei in neis:\n",
    "                    if 0<=nei[0]<=m-1 and 0<=nei[1]<=n-1:\n",
    "                        if grid[nei[0]][nei[1]]==0 and nei not in visited:\n",
    "                            visited.add(nei)\n",
    "                            count[nei[0]][nei[1]]+=1\n",
    "                            distance[nei[0]][nei[1]]+=d+1\n",
    "                            queue.append((nei[0],nei[1],d+1))\n",
    "\n",
    "        ans=2147483647\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if count[i][j]==len(starts):\n",
    "                    ans=min(ans,distance[i][j])\n",
    "        return ans if ans<2147483647 else -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestDistance(self, grid: List[List[int]]) -> int:\n",
    "        Row, Col = len(grid), len(grid[0])\n",
    "\n",
    "        canget_from_1 = [[0 for _ in range(Col)] for _ in range(Row)]  #空地，有多少个建筑物可以到达\n",
    "        dist_sum_from_1 = [[0 for _ in range(Col)] for _ in range(Row)]    #空地， 可以到达的建筑物们的距离和\n",
    "        cnt_1 = 0           #建筑物1的数量\n",
    "        for r in range(Row):\n",
    "            for c in range(Col):\n",
    "                if grid[r][c] == 1:\n",
    "                    cnt_1 += 1\n",
    "                    Q = [(r, c, 0)]\n",
    "                    visited = [[False for _ in range(Col)] for _ in range(Row)]\n",
    "                    while Q:\n",
    "                        i, j, d = Q.pop(0)\n",
    "                        for ni, nj in ((i-1,j), (i+1,j), (i,j-1), (i,j+1)):\n",
    "                            if (0 <= ni < Row) and (0 <= nj < Col) and (grid[ni][nj] == 0) and (visited[ni][nj] == False):\n",
    "                                canget_from_1[ni][nj] += 1\n",
    "                                dist_sum_from_1[ni][nj] += (d + 1)\n",
    "                                Q.append((ni, nj, d + 1))\n",
    "                                visited[ni][nj] = True\n",
    "        print(canget_from_1, dist_sum_from_1)\n",
    "        res = float('inf')\n",
    "        for r in range(Row):\n",
    "            for c in range(Col):\n",
    "                if grid[r][c] == 0:\n",
    "                    if canget_from_1[r][c] == cnt_1:\n",
    "                        res = min(res, dist_sum_from_1[r][c])\n",
    "        return res if res != float('inf') else -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestDistance(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        cnt = [[0] * n for _ in range(m)]\n",
    "        dist = [[0] * n for _ in range(m)]\n",
    "        s = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    s += 1\n",
    "                    q = deque()\n",
    "                    q.append((i, j))\n",
    "                    vis = set()\n",
    "                    d = 0\n",
    "                    while q:\n",
    "                        size = len(q)\n",
    "                        for _ in range(size):\n",
    "                            x, y = q.popleft()\n",
    "                            for w, e in (x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1):\n",
    "                                if 0 <= w < m and 0 <= e < n and grid[w][e] == 0 and (w, e) not in vis:\n",
    "                                    cnt[w][e] += 1\n",
    "                                    dist[w][e] += d + 1\n",
    "                                    q.append((w, e))\n",
    "                                    vis.add((w, e))\n",
    "                        d += 1\n",
    "        \n",
    "        ans = inf\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    if cnt[i][j] == s:\n",
    "                        ans = min(ans, dist[i][j])\n",
    "        return ans if ans != inf else -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestDistance(self, grid: List[List[int]]) -> int:\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        D = [[0] * m for _ in range(n)]\n",
    "        cnt = 0\n",
    "        cnt_from_1 = [[0] * m for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j] == 1:\n",
    "                    Q = []\n",
    "                    Q.append((i,j, 0))\n",
    "                    cnt += 1\n",
    "                    vis = [[0] * m for _ in range(n)]\n",
    "                    while Q:\n",
    "                        x, y, d = Q.pop(0)\n",
    "                        for nx, ny in [[x+1, y], [x-1,y], [x, y+1], [x, y-1]]:\n",
    "                            if 0<=nx<n and 0<=ny<m and grid[nx][ny] == 0:\n",
    "                                if vis[nx][ny] == 0:\n",
    "                                    vis[nx][ny] = 1 \n",
    "                                    D[nx][ny] += d + 1 \n",
    "                                    Q.append((nx, ny, d+1)) \n",
    "                                    cnt_from_1[nx][ny] += 1\n",
    "        ans = float('inf') \n",
    "        print(vis)\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j] == 0 and cnt_from_1[i][j] == cnt:\n",
    "                    ans = min(ans, D[i][j]) \n",
    "        print(D)\n",
    "        return ans if ans < float('inf') else -1\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestDistance(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        total_house = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    total_house += 1\n",
    "        reach = [[0] * n for _ in range(m)]\n",
    "        dist = [[0] * n for _ in range(m)]\n",
    "        def bfs(i, j):\n",
    "            queue = collections.deque()\n",
    "            queue.append([i, j, 0])\n",
    "            visit = set()\n",
    "            visit.add((i, j))\n",
    "            count = 1\n",
    "            while queue:\n",
    "                i, j, step = queue.popleft()\n",
    "                for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:\n",
    "                    x, y = i + dx, j + dy\n",
    "                    if 0 <= x < m and 0 <= y < n and (x, y) not in visit:\n",
    "                        if grid[x][y] == 1:\n",
    "                            count += 1\n",
    "                            visit.add((x, y))\n",
    "                        elif grid[x][y] == 0:\n",
    "                            reach[x][y] += 1\n",
    "                            dist[x][y] += step + 1\n",
    "                            queue.append([x, y, step + 1])\n",
    "                            visit.add((x, y))\n",
    "            return count == total_house\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    if not bfs(i, j):\n",
    "                        return -1\n",
    "\n",
    "        res = float(\"inf\")\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0 and reach[i][j] == total_house: \n",
    "                    res = min(res, dist[i][j])\n",
    "                    \n",
    "        return res if res != float(\"inf\") else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestDistance(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        total_house = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    total_house += 1\n",
    "        reach = [[0] * n for _ in range(m)]\n",
    "        dist = [[0] * n for _ in range(m)]\n",
    "        def bfs(i, j):\n",
    "            queue = collections.deque()\n",
    "            queue.append([i, j, 0])\n",
    "            visit = set()\n",
    "            visit.add((i, j))\n",
    "            count = 1\n",
    "            while queue:\n",
    "                i, j, step = queue.popleft()\n",
    "                for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:\n",
    "                    x, y = i + dx, j + dy\n",
    "                    if 0 <= x < m and 0 <= y < n and (x, y) not in visit:\n",
    "                        if grid[x][y] == 1:\n",
    "                            count += 1\n",
    "                            visit.add((x, y))\n",
    "                        elif grid[x][y] == 0:\n",
    "                            reach[x][y] += 1\n",
    "                            dist[x][y] += step + 1\n",
    "                            queue.append([x, y, step + 1])\n",
    "                            visit.add((x, y))\n",
    "            return count == total_house\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    if not bfs(i, j):\n",
    "                        return -1\n",
    "\n",
    "        res = float(\"inf\")\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0 and reach[i][j] == total_house: \n",
    "                    res = min(res, dist[i][j])\n",
    "                    \n",
    "        return res if res != float(\"inf\") else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestDistance(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        rds=[(0,1),(1,0),(-1,0),(0,-1)]\n",
    "        jianzhu=list()\n",
    "        dis=[[0 for i in range(n)] for j  in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==1:\n",
    "                    jianzhu.append((i,j))\n",
    "        def cal(x,y):\n",
    "            que=[(x,y,0)]\n",
    "            visited=set()\n",
    "            distmp=[[inf for i in range(n)] for j  in range(m)]\n",
    "            while(que):\n",
    "                i,j,d=que.pop(0)\n",
    "                distmp[i][j]=d\n",
    "                for rx,ry in rds:\n",
    "                    ni,nj=rx+i,ry+j\n",
    "                    if 0<=ni<m and 0<=nj<n and grid[ni][nj]==0 and (ni,nj) not in visited:\n",
    "                        visited.add((ni,nj))\n",
    "                        que.append((ni,nj,d+1))\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if grid[i][j]==0:\n",
    "                        dis[i][j]=dis[i][j]+distmp[i][j]\n",
    "                        \n",
    "        for x,y in jianzhu:\n",
    "            cal(x,y)\n",
    "                \n",
    "        ans=inf \n",
    "        print(\"over\")\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==0:\n",
    "                    ans=min(dis[i][j],ans)\n",
    "        if ans==inf:return -1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestDistance(self, grid: List[List[int]]) -> int:\n",
    "        row = len(grid)\n",
    "        col = len(grid[0])\n",
    "\n",
    "        num_can_reach = [[0 for _ in range(col)] for _ in range(row)]\n",
    "        dis = [[0 for _ in range(col)] for _ in range(row)]\n",
    "\n",
    "        \n",
    "        count_of_building = 0\n",
    "        direction = [(0,1), (0,-1),(1,0),(-1,0)]\n",
    "\n",
    "\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if grid[i][j] == 1:\n",
    "                        que = deque()\n",
    "                        que.append((i,j,0))\n",
    "                        count_of_building += 1\n",
    "                        visited = set()\n",
    "                        visited.add((i,j))\n",
    "                        while que:\n",
    "                            m, n, d = que.popleft()\n",
    "                            \n",
    "                            for dx, dy in direction:\n",
    "                                x = m + dx\n",
    "                                y = n + dy\n",
    "                                if 0 <= x < row and 0 <= y < col and grid[x][y] == 0 and (x,y) not in visited:\n",
    "                                    num_can_reach[x][y] += 1\n",
    "                                    dis[x][y] += (d + 1)\n",
    "                                    que.append((x, y, d + 1))\n",
    "                                    visited.add((x, y))\n",
    "\n",
    "        \n",
    "        \n",
    "\n",
    "        res = float(\"inf\")\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                if num_can_reach[i][j] == count_of_building and grid[i][j] == 0:\n",
    "                    res = min(res, dis[i][j])\n",
    "        return res if res != float(\"inf\") else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestDistance(self, grid: List[List[int]]) -> int:\n",
    "        # 设计一个访问记录dict，记录每个空白点到目的地的距离和以及被访问次数,访问许可\n",
    "        # 从每个建筑1触发第一次寻找到一个空白点时，更新visted，将次数加1，step叠加到举例，访问许可置为False\n",
    "        visited = defaultdict(lambda: [0, 0, True])\n",
    "        \n",
    "        # 新建一个建筑物列表，用于遍历\n",
    "        building_list = deque()\n",
    "        \n",
    "        # 找到所有建筑物\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    building_list.append((i, j))\n",
    "        \n",
    "        # 准备好4个邻居\n",
    "        directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]\n",
    "        \n",
    "        # count 计数，记录经历过几个building，方便在遍历过程中提前退出\n",
    "        count = 0\n",
    "        # 遍历每个建筑物，开始寻找这个建筑物附近的点，找到了就更新visted信息\n",
    "        for building in building_list:\n",
    "            count += 1\n",
    "            # 建立一个queue用来bfs\n",
    "            queue = deque()\n",
    "            queue.append(building)\n",
    "            step = 1\n",
    "            while queue:\n",
    "                total = len(queue)\n",
    "                while total > 0:\n",
    "                    ele = queue.popleft()\n",
    "                    for direction in directions:\n",
    "                        x = ele[0] + direction[0]\n",
    "                        y = ele[1] + direction[1]\n",
    "                        if x >= 0 and x < m and y >= 0 and y < n and grid[x][y] == 0:\n",
    "                            if (x, y) not in visited:\n",
    "                                visited[(x, y)] = [step, 1, False]\n",
    "                                queue.append((x, y))\n",
    "                            elif visited[(x, y)][2] == True:\n",
    "                                visited[(x, y)][0] += step\n",
    "                                visited[(x, y)][1] += 1\n",
    "                                visited[(x, y)][2] = False\n",
    "                                queue.append((x, y))\n",
    "                            else:\n",
    "                                pass\n",
    "                    total -= 1\n",
    "                step += 1\n",
    "            # 遍历完一个building后，将visited里面的访问开关打开，这样下一个就可以继续访问了\n",
    "            flag = False\n",
    "            for k in visited:\n",
    "                visited[k][2] = True\n",
    "                if visited[k][1] == count:\n",
    "                    flag = True\n",
    "            \n",
    "            # 遍历visited，如果根本没有一个点是所以building都访问过的，那么直接GG\n",
    "            if flag != True:\n",
    "                return -1\n",
    "        \n",
    "        # 遍历visited，找到最小的叠加数，如果次数都无法满足，直接返回-1\n",
    "        res = float(\"inf\")\n",
    "        for k in visited:\n",
    "            visited[k][2] = True\n",
    "            if visited[k][1] == count:\n",
    "                res = min(res, visited[k][0])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bfs(self, grid, start_row, start_col, total_dist):\n",
    "        x_dirs = [0, 0, -1, 1]\n",
    "        y_dirs = [1, -1, 0, 0]\n",
    "        n = len(grid)\n",
    "        m = len(grid[0])\n",
    "        queue = collections.deque([])\n",
    "        queue.append((start_row, start_col))\n",
    "        dist = dict()\n",
    "        dist[(start_row, start_col)] = 0\n",
    "        while queue:\n",
    "            row, col = queue.popleft()\n",
    "            for x_dir, y_dir in zip(x_dirs, y_dirs):\n",
    "                new_row = row + x_dir\n",
    "                new_col = col + y_dir\n",
    "                if 0 <= new_row < n and 0 <= new_col < m and (new_row, new_col) not in dist and grid[new_row][new_col] == 0:\n",
    "                    queue.append((new_row, new_col))\n",
    "                    dist[(new_row, new_col)] = dist[(row, col)] + 1\n",
    "                    total_dist[new_row][new_col][0] += dist[(new_row, new_col)]\n",
    "                    total_dist[new_row][new_col][1] += 1\n",
    "                    #print((start_row, start_col, new_row, new_col, dist[(new_row, new_col)]), total_dist[new_row][new_col])\n",
    "    def shortestDistance(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        m = len(grid[0])\n",
    "        total_dist = [[[0, 0] for _ in range(m)]for _ in range(n)]\n",
    "        n_buildings = 0\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j] == 1:\n",
    "                    self.bfs(grid, i, j, total_dist)\n",
    "                    n_buildings += 1\n",
    "        \n",
    "        #print(total_dist, n_buildings)\n",
    "\n",
    "        res = sys.maxsize\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if total_dist[i][j][1] == n_buildings:\n",
    "                    res = min(res, total_dist[i][j][0])\n",
    "\n",
    "        return res if res != sys.maxsize else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestDistance(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        dirs = {(0,1) ,(0,-1), (1,0), (-1,0)}\n",
    "\n",
    "        # count free land, grid[i][j] == 0\n",
    "        cnt = 0\n",
    "        ones = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    cnt += 1\n",
    "                elif grid[i][j] == 1:\n",
    "                    ones.append((i,j))\n",
    "        \n",
    "        if cnt == 0:\n",
    "            return -1\n",
    "        \n",
    "        # {(i,j):dis} total dis from 0 to all 1\n",
    "        total_dis = collections.defaultdict(int)\n",
    "        # total cnt from 0 to 1\n",
    "        total_cnt = collections.defaultdict(int)\n",
    "\n",
    "        for x, y in ones:\n",
    "            q = [(x,y,0)]\n",
    "            visit = set()\n",
    "            visit.add((x,y))\n",
    "            while q:\n",
    "                cur_x, cur_y, step = q.pop(0)\n",
    "                for dx, dy in dirs:\n",
    "                    nx = cur_x + dx\n",
    "                    ny = cur_y + dy\n",
    "                    if 0<=nx<m and 0<=ny<n and (nx,ny) not in visit and grid[nx][ny] == 0:\n",
    "                        nstep = step + 1\n",
    "                        total_dis[(nx, ny)] += nstep\n",
    "                        total_cnt[(nx, ny)] += 1\n",
    "                        visit.add((nx,ny))\n",
    "                        q.append((nx,ny,nstep))\n",
    "        \n",
    "        anw = int(1e9)\n",
    "        all_ = len(ones)\n",
    "        for p in total_cnt:\n",
    "            if total_cnt[p] == all_:\n",
    "                anw = min(anw, total_dis[p])\n",
    "        return anw if anw != int(1e9) else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestDistance(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        distance = collections.defaultdict(list)\n",
    "        direction = [[0, 1], [1, 0], [0, -1], [-1, 0]]\n",
    "        count = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    count += 1\n",
    "                    queue = [[i, j, 0]]\n",
    "                    visited = set()\n",
    "                    while queue:\n",
    "                        x, y, path = queue.pop(0)\n",
    "                        for dx, dy in direction:\n",
    "                            newx = x + dx\n",
    "                            newy = y + dy\n",
    "                            if 0 <= newx < m and 0 <= newy < n and (newx, newy) not in visited and grid[newx][newy] == 0:\n",
    "                                visited.add((newx, newy))\n",
    "                                queue.append([newx, newy, path+1])\n",
    "                                if (newx, newy) not in distance:\n",
    "                                    distance[(newx, newy)] = [path+1, 1]\n",
    "                                else:\n",
    "                                    distance[(newx, newy)][0] += path+1\n",
    "                                    distance[(newx, newy)][1] += 1\n",
    "        res = float('inf')\n",
    "        for key in distance:\n",
    "            # print(distance[key], count)\n",
    "            if distance[key][1] == count:\n",
    "                res = min(res, distance[key][0])\n",
    "        return res if res != float('inf') else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from typing import List\n",
    "from copy import deepcopy\n",
    "from collections import deque, defaultdict\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def shortestDistance(self, grid: List[List[int]]) -> int:\n",
    "        \"\"\"\n",
    "\n",
    "        :param grid:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        rooms = set()\n",
    "        blocks = set()\n",
    "        for k, v in enumerate(grid):\n",
    "            for k2, v2 in enumerate(v):\n",
    "                if v2 == 1:\n",
    "                    rooms.add((k, k2))\n",
    "                if v2 == 2:\n",
    "                    blocks.add((k, k2))\n",
    "        globalhit = set()\n",
    "        def get_val():\n",
    "            return math.inf\n",
    "\n",
    "        def get_map(start):\n",
    "            used = defaultdict(get_val)\n",
    "            dq1 = deque()\n",
    "            dq1.append((start, 0))\n",
    "            while dq1:\n",
    "                cur1, step = dq1.popleft()\n",
    "                if cur1 not in used:\n",
    "                    used[cur1] = step\n",
    "                else:\n",
    "                    if used[cur1] <= step:\n",
    "                        continue\n",
    "                    used[cur1] = step\n",
    "                directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]\n",
    "                for i in directions:\n",
    "                    newidx = cur1[0] + i[0], cur1[1] + i[1]\n",
    "                    if 0 <= newidx[0] < len(grid) and 0 <= newidx[1] < len(grid[0]) and grid[newidx[0]][newidx[1]] == 0 and newidx not in globalhit:\n",
    "                        if newidx not in used or used[newidx] > step + 1 :\n",
    "                            dq1.append((newidx, step + 1))\n",
    "            return used\n",
    "\n",
    "        mmlist = []\n",
    "        print('ok')\n",
    "        gm = defaultdict(int)\n",
    "        for i in rooms:\n",
    "            gm[(i[0], i[1])] = math.inf\n",
    "        for i in blocks:\n",
    "            gm[(i[0], i[1])] = math.inf\n",
    "        for i in rooms:\n",
    "            mm1 = get_map(i)\n",
    "            for k, v in enumerate(grid):\n",
    "                for k2, v2 in enumerate(v):\n",
    "                    if (k, k2) in rooms or (k, k2) in blocks:\n",
    "                        continue\n",
    "                    xxx = mm1.get((k, k2), math.inf)\n",
    "                    if xxx == math.inf:\n",
    "                        globalhit.add((k,k2))\n",
    "                    gm[(k, k2)] += xxx\n",
    "        print('ok2')\n",
    "        ans = math.inf\n",
    "        for k, v in enumerate(grid):\n",
    "            for k2, v2 in enumerate(v):\n",
    "                if (k, k2) in rooms or (k, k2) in blocks:\n",
    "                    continue\n",
    "                ans = min(ans, gm.get((k, k2), math.inf))\n",
    "        if ans == math.inf:\n",
    "            return -1\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "arrow = [\n",
    "    [0, 1],\n",
    "    [0, -1],\n",
    "    [1, 0],\n",
    "    [-1, 0],\n",
    "]\n",
    "\n",
    "class Solution:\n",
    "    def shortestDistance(self, grid: List[List[int]]) -> int:\n",
    "        # 统计中点有可能有两个\n",
    "        n = len(grid)\n",
    "        m = len(grid[0])\n",
    "        mit = [[[] for _ in range(m) ] for _ in range(n)]\n",
    "\n",
    "\n",
    "        def bfs(startNode):\n",
    "            queue = [startNode]\n",
    "            visited = set([startNode])\n",
    "            count = 0\n",
    "            while queue:\n",
    "                nt = []\n",
    "                for cx, cy in queue:\n",
    "                    # 判断是不是空地\n",
    "                    if grid[cx][cy] == 0:\n",
    "                        mit[cx][cy].append(count)\n",
    "\n",
    "                    for a, b in arrow:\n",
    "                        nx, ny  = cx + a, cy + b\n",
    "                        np = (nx, ny)\n",
    "                        if nx < 0 or ny < 0 or nx >= n or ny >= m: continue\n",
    "                        if np in visited: continue\n",
    "                        if grid[nx][ny] == 2 or grid[nx][ny] == 1: continue\n",
    "                        visited.add(np)\n",
    "                        nt.append(np)\n",
    "                count += 1\n",
    "                queue = nt\n",
    "\n",
    "        hosueCount = 0\n",
    "        for x in range(n):\n",
    "            for y in range(m):\n",
    "                if grid[x][y] == 1:\n",
    "                    bfs((x, y))\n",
    "                    hosueCount += 1\n",
    "\n",
    "         \n",
    "        res = inf\n",
    "        for x in range(n):\n",
    "            for y in range(m):\n",
    "                if grid[x][y] == 0:\n",
    "                    # print(mit[x][y])\n",
    "                    if  len(mit[x][y]) == hosueCount:\n",
    "                        # 判断空地是否能到达所有的房子\n",
    "                        res = min(res, sum(mit[x][y]))\n",
    "        return res if res != inf else -1\n",
    "'''\n",
    "[\n",
    "    [1,0,2,0,1],\n",
    "    [0,0,0,0,0],\n",
    "    [0,0,1,0,0]\n",
    "]\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestDistance(self, grid: List[List[int]]) -> int:\n",
    "        distance = []\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        for i in range(m):\n",
    "            t = [[] for _ in range(n)]\n",
    "            distance.append(t)\n",
    "        d = [[0] * n for _ in range(m)]\n",
    "        start = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    start.append([i, j])\n",
    "                    distance[i][j] = [0]\n",
    "        for k, pos in enumerate(start):\n",
    "            q = [pos]\n",
    "            while q:\n",
    "                x, y = q.pop(0)\n",
    "                if x == 1 and y == 0:\n",
    "                    print(pos)\n",
    "                if x+1 < m and grid[x+1][y] == 0 and d[x+1][y] == k:\n",
    "                    distance[x+1][y].append(distance[x][y][-1] + 1)\n",
    "                    d[x+1][y] += 1\n",
    "                    q.append([x+1, y])\n",
    "                if x > 0 and grid[x-1][y] == 0 and d[x-1][y] == k:\n",
    "                    distance[x-1][y].append(distance[x][y][-1] + 1)\n",
    "                    d[x-1][y] += 1\n",
    "                    q.append([x-1, y])\n",
    "                if y+1 < n and grid[x][y+1] == 0 and d[x][y+1] == k:\n",
    "                    distance[x][y+1].append(distance[x][y][-1] + 1)\n",
    "                    d[x][y+1] += 1\n",
    "                    q.append([x, y+1])\n",
    "                if y > 0 and grid[x][y-1] == 0 and d[x][y-1] == k:\n",
    "                    distance[x][y-1].append(distance[x][y][-1] + 1)\n",
    "                    d[x][y-1] += 1\n",
    "                    q.append([x, y-1])\n",
    "        print(distance)\n",
    "        ans = 1000000\n",
    "        for i in range(m):\n",
    "            for j in range(n):    \n",
    "                if grid[i][j] == 0 and distance[i][j] and len(distance[i][j]) == len(start):\n",
    "                    ans = min(ans, sum(distance[i][j]))\n",
    "        if ans == 1000000:\n",
    "            return -1\n",
    "        else:\n",
    "            return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def shortestDistance(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        direction = [(0,1),(1,0),(-1,0),(0,-1)]\n",
    "        building = []\n",
    "\n",
    "        def create_building_map(x,y):\n",
    "            stack = deque()\n",
    "            building_map = [[-1]*n for _ in range(m)]\n",
    "            stack.append((x,y))\n",
    "            visited = set()\n",
    "            visited.add((x,y))\n",
    "            step = 0\n",
    "            while(stack):\n",
    "                l = len(stack)\n",
    "                for i in range(l):\n",
    "                    cx,cy = stack.popleft()\n",
    "                    building_map[cx][cy]=step\n",
    "                    for dx,dy in direction:\n",
    "                        nx,ny = cx+dx,cy+dy\n",
    "                        if (nx,ny) not in visited and 0<=nx<m and 0<=ny<n and grid[nx][ny]==0:\n",
    "                            visited.add((nx,ny))\n",
    "                            stack.append((nx,ny))\n",
    "                step+=1\n",
    "            return building_map\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==1:\n",
    "                    building.append(create_building_map(i,j))\n",
    "        def check_route(x,y):\n",
    "            distance = 0\n",
    "            for cell in building:\n",
    "                if cell[i][j]==-1 or cell[i][j]==0:\n",
    "                    return -1\n",
    "                distance+=cell[x][y]\n",
    "            return distance\n",
    "        min_distance = float('inf')\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                temp = check_route(i,j)\n",
    "                if temp==-1:\n",
    "                    continue\n",
    "                min_distance = min(min_distance,temp)\n",
    "        return min_distance if min_distance!=float('inf') else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def shortestDistance(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        direction = [(0,1),(1,0),(-1,0),(0,-1)]\n",
    "        building = []\n",
    "\n",
    "        def create_building_map(x,y):\n",
    "            stack = deque()\n",
    "            building_map = [[-1]*n for _ in range(m)]\n",
    "            stack.append((x,y))\n",
    "            visited = set()\n",
    "            visited.add((x,y))\n",
    "            step = 0\n",
    "            while(stack):\n",
    "                l = len(stack)\n",
    "                for i in range(l):\n",
    "                    cx,cy = stack.popleft()\n",
    "                    building_map[cx][cy]=step\n",
    "                    for dx,dy in direction:\n",
    "                        nx,ny = cx+dx,cy+dy\n",
    "                        if (nx,ny) not in visited and 0<=nx<m and 0<=ny<n and grid[nx][ny]==0:\n",
    "                            visited.add((nx,ny))\n",
    "                            stack.append((nx,ny))\n",
    "                step+=1\n",
    "            return building_map\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==1:\n",
    "                    building.append(create_building_map(i,j))\n",
    "        def check_route(x,y):\n",
    "            distance = 0\n",
    "            for cell in building:\n",
    "                if cell[i][j]==-1 or cell[i][j]==0:\n",
    "                    return -1\n",
    "                distance+=cell[x][y]\n",
    "            return distance\n",
    "        min_distance = float('inf')\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                temp = check_route(i,j)\n",
    "                if temp==-1:\n",
    "                    continue\n",
    "                min_distance = min(min_distance,temp)\n",
    "        return min_distance if min_distance!=float('inf') else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestDistance(self, grid: List[List[int]]) -> int:\n",
    "        from collections import deque\n",
    "        res=[]\n",
    "\n",
    "        directions=[(0,1),(0,-1),(1,0),(-1,0)]\n",
    "\n",
    "        def Is(x,y):\n",
    "            return x>=0 and x<len(grid) and y>=0 and y<len(grid[0])\n",
    "\n",
    "        #从每个建筑物（即1）出发，得到其到每个空地0的距离\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j]==1:\n",
    "                    queue=deque([(i,j)])\n",
    "                    dis=-1\n",
    "                    distance=[[float(\"inf\")]*len(grid[0]) for _ in range(len(grid))]\n",
    "                    distance[i][j]=0\n",
    "                    visited=set((i,j))\n",
    "                    while queue:\n",
    "                        dis+=1\n",
    "                        for _ in range(len(queue)):\n",
    "                            x,y=queue.popleft()\n",
    "                            for direction in directions:\n",
    "                                new_x=x+direction[0]\n",
    "                                new_y=y+direction[1]\n",
    "                                if Is(new_x,new_y) and grid[new_x][new_y]==0 and (new_x,new_y) not in visited:\n",
    "                                    visited.add((new_x,new_y))\n",
    "                                    queue.append((new_x,new_y))\n",
    "                                    distance[new_x][new_y]=dis+1\n",
    "                    res.append(distance)\n",
    "        n=len(res)\n",
    "        minDis=float(\"inf\")\n",
    "        ########################选址###############################\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j]==0:\n",
    "                    minDis=min(minDis,sum(res[k][i][j] for k in range(n)))\n",
    "        return minDis if minDis<float(\"inf\") else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "from queue import Queue\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.moves = [[0, -1], [1, 0], [0, 1], [-1, 0]]\n",
    "\n",
    "    def get_neighbor(self, frontier, grid):\n",
    "        for m in self.moves:\n",
    "            r, c = frontier[0] + m[0], frontier[1] + m[1]\n",
    "            if 0 <= r and r < self.R and 0 <= c and c < self.C and grid[r][c] != 2:\n",
    "                yield r, c\n",
    "\n",
    "    def is_blocked(self, home, grid):\n",
    "        for m in self.moves:\n",
    "            r, c = home[0] + m[0], home[1] + m[1]\n",
    "            if 0 <= r and r < self.R and 0 <= c and c < self.C and grid[r][c] == 0:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "    def shortestDistance(self, grid) -> int:\n",
    "        homes = []\n",
    "        self.R = len(grid)\n",
    "        self.C = len(grid[0])\n",
    "        bfs_sum = np.zeros((self.R, self.C), dtype=int)\n",
    "        num_space = 0\n",
    "        INT_MAX = self.R * self.C*100\n",
    "        for r in range(self.R):\n",
    "            for c in range(self.C):\n",
    "                if grid[r][c] == 1:\n",
    "                    homes.append((r, c))\n",
    "                if grid[r][c] > 0:\n",
    "                    bfs_sum[r][c] = INT_MAX\n",
    "                if grid[r][c] == 0:\n",
    "                    num_space+=1\n",
    "        if num_space==0:\n",
    "            return -1\n",
    "\n",
    "        # 测试连通性\n",
    "        if len(homes)>1:\n",
    "            home = homes[0]\n",
    "            q = Queue()\n",
    "            visited = np.zeros((self.R, self.C), dtype=bool)\n",
    "            q.put((home, 0))\n",
    "            visited[home[0]][home[1]] = True\n",
    "            visited_homes = set()\n",
    "\n",
    "            while not q.empty():\n",
    "                frontier, distance = q.get()\n",
    "                for nb in self.get_neighbor(frontier, grid):\n",
    "                    r, c = nb\n",
    "                    if not visited[r][c]:\n",
    "                        visited[r][c] = True\n",
    "                        if grid[r][c] == 0:\n",
    "                            q.put((nb, distance))\n",
    "                        elif grid[r][c] == 1:\n",
    "                            visited_homes.add((r, c))\n",
    "            if len(visited_homes) != len(homes) - 1:# 能连通其他home\n",
    "                return -1\n",
    "\n",
    "        for home in homes:\n",
    "            if  self.is_blocked(home, grid) :\n",
    "                return -1\n",
    "\n",
    "            q = Queue()\n",
    "            visited = np.zeros((self.R, self.C), dtype=bool)\n",
    "            q.put((home, 0))\n",
    "            visited[home[0]][home[1]] = True\n",
    "\n",
    "            this_bfs_sum = np.full((self.R, self.C),INT_MAX, dtype=int)\n",
    "            while not q.empty():\n",
    "                frontier, distance = q.get()\n",
    "                distance += 1\n",
    "                for nb in self.get_neighbor(frontier, grid):\n",
    "                    r, c = nb\n",
    "                    if not visited[r][c]:\n",
    "                        visited[r][c] = True\n",
    "                        if grid[r][c] == 0:\n",
    "                            this_bfs_sum[r][c] = min(distance,this_bfs_sum[r][c])\n",
    "\n",
    "                            q.put((nb, distance))\n",
    "            bfs_sum +=this_bfs_sum\n",
    "            print(bfs_sum)\n",
    "            print()\n",
    "\n",
    "        res = int(bfs_sum.min())\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 给你一个 m × n 的网格，值为 0 、 1 或 2 ，其中:\n",
    "\n",
    "# 每一个 0 代表一块你可以自由通过的 空地 \n",
    "# 每一个 1 代表一个你不能通过的 建筑\n",
    "# 每个 2 标记一个你不能通过的 障碍 \n",
    "class Solution:\n",
    "    def shortestDistance(self, g: List[List[int]]) -> int:\n",
    "        v = {}\n",
    "        m = len(g)\n",
    "        n = len(g[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if g[i][j]==0:\n",
    "                    v[(i, j)] = {}\n",
    "        num = 0 \n",
    "        def f(i, j):\n",
    "            st = (i, j)\n",
    "            s = [(i, j)] \n",
    "            dis = 0 \n",
    "            while s:\n",
    "                tmp = []\n",
    "                dis += 1\n",
    "                for i, j in s:\n",
    "                    for x, y in [[0,1], [0,-1], [1,0], [-1,0]]:\n",
    "                        x += i \n",
    "                        y += j \n",
    "                        if (0<=x<m) and (0<=y<n):\n",
    "                            if g[x][y]==0:\n",
    "                                if st not in v[(x, y)]:\n",
    "                                    v[(x, y)][st] = dis \n",
    "                                    tmp.append([x, y]) \n",
    "                s = tmp \n",
    "      \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if g[i][j]==1:\n",
    "                    f(i, j) \n",
    "                    num += 1 \n",
    "        if num==0:\n",
    "            return -1 \n",
    "        v = {j:v[j] for j in v if len(v[j])==num}\n",
    "        if not v:\n",
    "            return -1 \n",
    "        s = [sum(j.values()) for j in v.values()]\n",
    "        return min(s)\n",
    "        \n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestDistance(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        visited = collections.defaultdict(set)\n",
    "        q = []\n",
    "        house_cnt = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    q.append([i, j, i * n + j])\n",
    "                    visited[(i, j)].add(i * n + j)\n",
    "                    grid[i][j] = -1\n",
    "                    house_cnt += 1\n",
    "                if grid[i][j] == 2:\n",
    "                    grid[i][j] = -2\n",
    "        step = 0\n",
    "        dirs = [0,1,0,-1,0]\n",
    "        while q:\n",
    "            next_q = []\n",
    "            for i, j, idx in q:\n",
    "                for k in range(4):\n",
    "                    ni, nj = i + dirs[k], j + dirs[k + 1]\n",
    "                    if ni < 0 or nj < 0 or ni >=m or nj >=n or idx in visited[(ni, nj)] or grid[ni][nj] == -2 or grid[ni][nj] == -1:\n",
    "                        continue\n",
    "                    grid[ni][nj] += step + 1\n",
    "                    visited[(ni, nj)].add(idx)\n",
    "                    next_q.append([ni, nj, idx])\n",
    "            step += 1\n",
    "            q = next_q\n",
    "\n",
    "        ret = inf\n",
    "        #print(grid)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] > 0 and len(visited[(i, j)]) == house_cnt:\n",
    "                    ret = min(ret, grid[i][j])\n",
    "        return ret if ret < inf else -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestDistance(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        visited = collections.defaultdict(set)\n",
    "        q = []\n",
    "        house_cnt = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    q.append([i, j, i * n + j])\n",
    "                    visited[(i, j)].add(i * n + j)\n",
    "                    grid[i][j] = -1\n",
    "                    house_cnt += 1\n",
    "                if grid[i][j] == 2:\n",
    "                    grid[i][j] = -2\n",
    "        step = 0\n",
    "        dirs = [0,1,0,-1,0]\n",
    "        while q:\n",
    "            next_q = []\n",
    "            for i, j, idx in q:\n",
    "                for k in range(4):\n",
    "                    ni, nj = i + dirs[k], j + dirs[k + 1]\n",
    "                    if ni < 0 or nj < 0 or ni >=m or nj >=n or idx in visited[(ni, nj)] or grid[ni][nj] == -2 or grid[ni][nj] == -1:\n",
    "                        continue\n",
    "                    grid[ni][nj] += step + 1\n",
    "                    visited[(ni, nj)].add(idx)\n",
    "                    next_q.append([ni, nj, idx])\n",
    "            step += 1\n",
    "            q = next_q\n",
    "\n",
    "        ret = inf\n",
    "        print(grid)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] > 0 and len(visited[(i, j)]) == house_cnt:\n",
    "                    ret = min(ret, grid[i][j])\n",
    "        return ret if ret < inf else -1\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
